perm filename MAPS.BIG[E81,JMC] blob
sn#619399 filedate 1981-10-10 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00005 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002
C00025 00003 We can regard coloring the dropped countries as a process of
C00029 00004 Notes:
C00039 00005 Results of coloring the map of the U.S.
C00043 ENDMK
C⊗;
COLORING MAPS AND THE KOWALSKI DOCTRINE
Kowalski (l974) enunciated the doctrine expressed by the formula
program = logic + control
The formula isn't precise, and it won't be precise until
someone proposes a precise and generally accepted notion of how
control is to be added to an expression of the logic of a program.
Nevertheless, the idea is attractive, and I believe it can be made to work
for some interesting class of programs. It is analogous to my comparison
of epistemology and heuristics or Chomsky's competence and performance.
Pereira and Porto (1981) give a logic program for coloring planar
maps with four colors and discuss how "intelligent
backtracking" can reduce the search involved in coloring a map from that
done by a straightforward PROLOG execution of the same
program.
The discussion by Pereira and Porto treats coloring maps purely as
an example of logic programming, and the improvements they discuss apply
to all logic program systems. We shall consider two mathematical ideas
about map coloring that go back to Kempe (1879), the paper containing the
original false proof of the four color theorem. While Kempe's proof
was false, the ideas are good and were used in almost all subsequent work
including the recent successful proof.
The question is whether an algorithm
involving these ideas can be regarded as a form of control adjoined to
the basic logic program or whether they necessarily involve a new program.
If they are to be regarded as control structures, it is not yet clear how
they are best expressed. Of course, it is not hard to write a completely
new program in PROLOG or any other language expressing the algorithms, but
perhaps they can also be regarded as control attached to the Pereira-Porto logic.
2. The Pereira-Porto logic program
There are two parts. The first expresses that the adjacent
countries must have different colors by listing the pairs of colors that
may be adjacent. We have
(1) next(yellow,blue).
next(yellow,red).
next(yellow,green).
next(blue,yellow).
etc. for all pairs of distinct colors.
The remaining PROLOG statement is distinct for each map. For the
map of Figure 1, which they use as an examplE,
(3 inches here for figure 1)
Figure 1
it is
(2) goal(R1,R2,R3,R4,R5,R6) ← next(R1,R2),next(R1,R3),next(R1(R5),
next(R1,R6),next(R2,R3),next(R2,R4),next(R2,R5),next(R2,R6),next(R3,R4),
next(R3,R6),next(R5,R6).
where each literal expresses the fact that a particular pair of adjacent
regions must be compatibly colored.
Pereira and Porto give a tpace ob the execution of the program by
standard depth farst PROLOG. They point out that when an attempt to
satisfy a literad fails, because the two adjacent regions mentioned have
been assigned the same cOlor, standard PROLOG wilL take back
the most recent asqignment of a color evenif the region most recently
@
←Y←e∃HAoCLA]KSQQKdA=LAiQ=gBAS9m←Ym∃HAS\↓iQJA%]G←[ACiSE%YSir8@A)Q∃Sd~∃%]aKY1SOK]PAECG-ieCG-S]NA]SYXA
QC]O∀AiQJ↓G←Y←HAWLA=]JA←α1βS#*βK↔∨L{;L4V;'['v9βS#*β';∂}kCπSN∪'3''I84(hP&π9ε{WSON#↔Iβ&yβ3?>K
βC⊗{↔Kπnk';≥εkπeβ⊗+π∂Qπ+;OgoβπS#-#'∂πdceβπv 4+∂}k7↔;"βS#π ∧π&F≡4εO~
.W∨"
⎇f*ε]xLT→>_-↑≠→(
|H_
MβstaH897s\0p
ming system0~∃oSQPASiLAgiC9ICeH↓oCrA=HAI←%]NAg∃CeGQ∃bXAiISaaS9H
β?6+Iβ''→β?←pβ≠↔↔"p4*#|εv/6↑!Bπ≡T
6F␈]LBε∞L9rπ⊗\<⊗fb∞Mε∂".&N.d⊗v"\↔∨J∞:F∂&]\Vw"
x D∞~→(
Ss∪hq"\∀M||X;$Y|@⊂≥42P![v7y4[3P0w→⊂77`4 givE qp This virtu@∀AoSi!←khA∧AMSO!h\
∀4∀∪≥KYKeiQ∃YKgf0~∀ES9iKYY%H∂π; βπ∂←#@⊗∞==⊗v:$F}∂=dw"ε\≥6*α∧∧*$9Y⊂
→∀P )nto a good colOrifg
program. Ifdeed we shall argue that iT doesn't Even do fuLl jestice tk the
lodπSFA=LAiQ∀Aae←≥aCZ\α↓αS=π≠↔*∞MεO~∞|Rεv\\Bπ'⎇tεN&\≡2ε↑d 6.oU`hPβ"C!&kHλ
,9≥0m≥Yh∃
(≠8.↓"C"A→y;<T
≠p→λ82y4_x9P9[vrww→P9z4[6⊂2p\64ri
FE77]4qrrλ:40zλ1wzw≥94ryH;tz4λ:492YP7q⊂→2{riλ72tsZ17y9H892yYw:εE≠7P8)≠q62vK⊂⊂'7H6pz:→y⊂47]P:42H92yjλ7s⊂*~2P6p\⊂4yP_wv7i→r⊗⊂*~2y2P~yP0v≥p|qFB0P1`/lor available For such acountpy. This suggests "redu@
S]NAQQJA[¬`DAEd~∃eK5←mS]≤AgkG AG←k9ieSKLAC]H↓I←S]≤A←kd↓ieSC0[C]H5Kee←HAG←Y=eS]N↓←\Ai!J~∃e∃IkGK⊂A[C`0AG←]→SIK]PAiQCPA←]G∀AiQJ↓eKIk
KHA[¬`ASf↓G←Y←IKHXAQQJAG=Y←eS9N~∃G¬\AEJ↓KqiK9IKHAQ↑AiQ∀A←[SQiKHA
←k]iISKf\4∀~∀∪QQJAS⊃KBASLAKmK8A[←e∀Aa←o∃eMkX0AEKG¬kgJA∃YS[S9CiS]≤AG←k9ieSKLAoSi ~∃iQIKJA←HAMKo∃dA]K%OQE←IfA[CdAeK[=mJAK9←kOP↓]KSO!E←ef↓Me←Z↓g←[J↓←iQKH~∃G←U]ieS∃fAg↑↓iQCh↓iQKr↓QCmJ↓iQeK∀A←dA→KoKd↓]KSO!E←ef↓C]HA
C\Ai!K[gK1mKfA J~∃e∃[←mK⊂\@A)!KeKM=eJXAQQJAe∃IkGi%←\AaI←GKgLAgQ←UYHAE∀AG←]QS]kK⊂Ak]i%XAB~)G←[a1KiKYdAeKIUGKHA5C`ASLA←Ei¬S]KH↓S\Ao!SGPA¬YXAG=k]ie%KfAQ¬mJACPAYKCMhAM←Ud~∃]∃SOQE=ef\~(@A)Q∀A[CaLA←LAQQJAgQCiKf↓←LAi!JA*]L\AC]⊂~∃iQ∀AG←k9ieSKLA←LA∃ke←a∀XAβg%BXAβ→eSGB↓C]HAM←kiP↓β[Ke%GBAC1XAeK⊃kGJ~)i↑A]UYXA[¬afAo!K\AG=k]ie%KfAo%iPAi!eKJA=dAMK]KdA]∃SOQE=efACIJAgk
GKgg%mKYr4∃KYS5S]Ci∃H~∀~(∪→SW∃oSgJ↓iQJA5C`A←_A
SOUeJ@b↓eKIk
KfAi<AiQJ↓K[aidA[C`8@@~∃QQkfA]JA[CdAeK[=mJAG=k]ied@hAo%iPAi]↑A]K%OQE←IfAC]⊂AG←k9ier@TAoSi AiQe∃J~∃]∃SOE←If\@AQQSfA1KCmKLACYX↓iQJAIK[CS9S]NA
←k]iISKfA]SiPAQQeKJ↓←dAM∃oKd~)]KSO!E←ef0Ag↑AQQJAg∃G←]H↓GsGY∀A←LAIKIkGQS←\A1KCmKLAiQJ↓]kYX↓[C`\4∃eKIUGKHA5C`\@↓)QKe∃M←eJ0AoQK8AoJA
←Y←e∃HAS\↓iQJAIKmKeMJA←e⊃Kd~∀DXdXf0lXhXTXAKC
PAG←U]ier↓SfAG=Y←eK⊂AoSi!←khA
QC]O%]NAi!J~∃G=Y←dA=LAC]dAaeKYS←kg1rAG←1←eKH↓G←k]Qer\~(~∀∪∪_AiQJ↓ae←OIC[[KHAaKe→←e[f↓iQSf↓eKIk
iS←\↓EKM←IJAQJ↓oeSi∃fAiQ∀~∃O←¬XAgi¬iK[K9hXAQ∀AoSY0AoeSQJ~∀~(∪O←C0Q$bYHdY$f1$hY$TY$lR↓>A]KahQ$b1$dRY9KqhQHbY$f$Y]KqPQ$bYHlRX~)]Kqh!$dY$LRY]KahQ$d1$lRY9KqhQHfY$l$Y]KqPQ$dYHhRY]∃qhQ$LY$hR1]Kqh!$bY$TRX~∃9KqhQHdY$j$Y]KqPQ$jYHlR\~(~∀∪)!SfA!I∨→∨∞↓ae←OICZAo%YXAeU\AoSQPA←]1rAiQ∀A[←gPAY←G¬X~∃E¬GWie¬GWS]≤\@A≥¬[KYr0ACMi∃dA$b↓QCfA KK\A
Q←gK8ACeE%ieCe%YrXAMKmKe¬X~∃m¬YkKf↓oSYX↓QCmJ of the variables R1,R2,R3,R6,R4,and R5, but
once a value has been found that is compatible with the previously
determined variables, it won't have to be changed again.
The new PROLOG program is logically equivalent to the previous
program because it is just a rearrangement of the literals of a
conjunction. However, the programmer has done the control. The
interesting question is whether the reduction can be expressed in some way
that can be regarded as adding control to the original logic, i.e.,
without changing the original logic.
4. Kempe transformations
Another idea of Kempe's can be used to strengthen the reduction
process, but regarding it as mere control added to the original logic program
seems even harder.
The strengthened reduction procedure also removes countries with
four neighbors so that the reduced map contains only countries with five
or more neighbors. The validity of this reduction depends on the following
Kempe proof
that if we have colored a partial map and want to add a country
With four neighbors, we can always revise the coloring of the partial map
to permit coloring the four neighbor country.
If fewer than four colors have been used to color the neighbors,
there is no problem, so suppose that the four neighbors have been colored
with four different colorq as shown in Figure 2.
(3 inches here for figure 2)
Figure 2
Consider the set S of all countries that can be reached from the
blue Country A On top of Figure 2 by a path going through only blue and
yellow countries. S iq called the blue-yellow Kempe component of
countpy A. There are two cases* Either it Contains country C or not. If
not, we Recolor the partial Map by reversing blue and yellOw on all
countries in S. This sTill leaves the
partial Map pRoperly coLored.
Since
λ¬&@A⊃←KfA9←hAG=]iCS8@AεX↓α@Ae∃[CS]LAsKY1←n~∃]QSYJAα@A!CfAE∃G←[J↓s@↔3d¬w:R∧
FFO4
V∞↑↑4ε⊗g\Tε∂6≥→F∞⊗LTπ&z[π&.l@π&FQQ&≡}MxM≥Yh≥
t⊗C!↓"B2-d≥~→$
⎇~→.$_x<lUλ∀h∧{{]≥;\c!(kλ∩%l+λ∃
<Y(
≡h_ =_:;D
yH_,MX8q-nλ_sn]]≤Z,↑h→TM⎇(⊂ ∞Mh⊂h\8z
|H≥z
≤zβ"M≡h_{mM|Y9∧Y→1$
|H≡,]≠≠ueDλ∃~]H≥~↑Y(⊂l≥Y[u∧Y(_$∞Y9,@y2rwλ1t0t[⊂397[P!εE≥7P"
1<P*~2P:7\7v7s↑P7s⊂≥42P8≠0p∞e or sphere), so that↓BAeK⊂[OeK∃\AπK5aJ
∃β#@⊗∞n8f␈⊗β8=
≥{H_.∞≠~0∩Y⊂:7P≥42P)→r⊂
grean Kempe compOnent ob B↓oSYX↓[C@/*α (,}&.∞eDεf.≡h
-lh≤Y,D_9P-≥_8[T≥≠h={≠p→λ,∪εEβEj4→P30q]⊂:40]⊂0P!≠8rV|Yv67`7 path froM A to C blocks a reD-cre@∃\⊂∀+α↔&BhM⎇(⊂@∞MβP" is where @]JAQCYJAkgα+⊃βSF)β≠π≥!βS#∂!βS#*β7πA∧¬↔4≠{@⊂_P86 [2BE /p spHere.
λ
This Justi@→S@↔M∧+3'↔L¬f∂&≥lrε≡}]g'⊗≤Z2π>≡Mαε6β⎇0→λ72tcZ13q9H4w⊂ 4he¬
@IKIkGβ#'?9πβK/∂-≠M)↓∧K→β←*β#π[*β∂?3|ε&."⊂λ∞<]~,≥λ≠8.∧_;Y∧∞x;]∧∞≠h_,Lλ_#!{⎇;NN↑(⊂≠Zz4⊂#≠zy⊂'→tst1≠y9V⊂≥rP1`[⊂27P≤wV⊂!≥z⊂;rH6p|P~0{2P≥5P6wY4s<P≥42FE≤92{$[zyP![v7y4[3P1<H6rpw≤β of a CeMpe transf@=eSCi%←\\~(~∀&␈+Iβ'oβK?[.!β∂?d{C';8∧ε∞f⎇z&O&
Pπ&F]`λ∞,9≥0l↑h≥~T≠8<∧↑(⊂→→x2pz→r64FB297x≤4s3@ countries with dour or fEwar neighbors, colorpεAiQ∀AeKIUGKHA5C`~∃∃qQCkMiSmK1rXAC9HAiQ∃\AG←1←efAQQJAII←aaK⊂AG←k9ieSKLAS\AQQJAe∃mKeg∀A←eI∃d~∃kMS]NA-K[aJ↓ieC]MM←e[¬iS←]LAoQK8A]KG∃cgCed\~∀~(~∀j\↓%KCY%uSMN↓iQJAIKIkGQS←\A¬YO←e%iQZA rAG←9ie←X↓←DAi!JA!KIKSeB5!←ei<AY←O%F~∀~(∩~∀∪→e←ZAQQJAa=S]hA=LAmS∃nA←L↓YWOSAae←≥eCK[%]NXAMkGGKMgSmK1r~∃e∃IkGS9NAiQ∀A[C`↓ErAa=gia←9S]NA
←k]iISKfA]SiPAQQeKJ↓←dAM∃oKdA9KSOQ ←ef~)SfAC8AKqC5aYJA=LABA5←eJA≥K]Ke¬XA]←QS←\@4AiQCPA←LA∧A↓a7A←gia=]CEY∀~∃mCISCEY∃:\@A∧AmCe%CEYJ↓S\Ai!JAE←⊃rA←L↓BAGY¬kgJA%fAa←Mia←]¬EYJA%L~∃]<A[CiQKdAQ=nAiQ∀A←iQ∃dAmCISCEY∃fACe∀ACgg%O]KH0AiQKIJASf↓BAmC1kJAM=d~∃i!SfAm¬eSCE1JAiQ¬hAGCUgKfA¬YXAi!JAO←¬YfAS9m←Ym%]NAi!ChAm¬eSCE1J~∃i<AEJAMCiSg→SKH\AπYK¬eYrA¬]rAa=gia←9CEYJ↓mCeS¬EYJA
C\AE∀Aa←gQa←]K⊂~∃i↑↓iQJA∃]H\@↓≠←eK=mKdX↓Ukgh↓CfAS8AiQJ↓[C`A
←Y←e%]NAaI←EYK4XAa←Mia←]%]N~∃M←[JAYCeSC YKfA5CrAe∃[←mJ↓K]←k≥PAO←¬YfAS9m←Ym%]NA←QQKdAYCeSC YKfAM↑~∃i!ChAi!KrAS8Aike8AEKG=[JAa=gia←9CEYJ8~∀~∀%∪LAi!KeJA]KeJA=]YrA=]JAgQCOJA=LAa←Mia←]∃[K]h0AoJA
←kYH↓eKOCIH~∃a=gia←9K[K]PACfA∧AGCg∀A←LAMKYKGQS]NAQQJAM%eghA≥←CXAQ↑AEJ↓CiiK5aiKH0~∃iQ∀Aa←gQa←]C YJAm¬eSCE1KfAE∃S]NAIKUKGQKHAM=dAgK1KGiS=\\@A!←oKm∃dXAi!Sf~∃]←kYI8OhAaIKmK]PAiQJ↓gKYK
iS←\↓←LAB↓mCeS¬EYJAA←gia=]CEY∀AS\AQQJAg∃G←]H4∃giC≥J\@AQQKeK→←eJX↓iQJAA←gia=]K[K9hAae=GKgf↓gQ←k1HAEJ↓G←[a1KiKH↓EKM←IJ~∃C9rAO←¬YfACIJAgK1KGiK⊂AM←d↓CiiK5ah\~(~∀∪)!JAa←Mia←]¬ESYSQrA←L↓BAmCISCEY∀ASfA∃qaeKMgKHA rABAA←gia=]K[K9h~∃Y∃[[B\A
←d↓KqC[AYJXAQQJAa=gia←9CESY%irA←_A↓S7Hi:ASLAKqaIKggK⊂AEr~)iQJA→←e[k1B~∀~(∪↓S6Q$dA$L\+$h8Q]KqPQ$dYHhR@λ↓]Kqh!$fY$PRS:\4∀~∃≥=iSGJ↓iQCh↓←kdAEkSGV↓eKG←≥]SiS=\A←L↓iQJAA←gi←A←]CE%YSir↓←LA↓%7$i:↓Sf~∃ CgKH↓←\Ai!JAgs5[Kied\@A/∀AgCr↓iQCh↓oQCi∃mKdA
←Y←eLACeJ↓CggS≥]KHAQ↑~∃↓%7$e:↓C]HA↓S7$gtXABA
←[aCQSEYJ↓G←Y←HAGC\↓EJAM=k]HA→←dA↓%7$i:8@A/J4∃I←\≥hAQCYJAi↑↓K]k[∃eCiJ↓iQJAA←ggS YJACMgSO]∃[K]iLAi↑A↓S7$etAC]H↓↓S7$M:\~∃∧Aae←≥eCZA]←kYH↓QCmJ↓i↑AI<A[←e∀Ao←e,Ak]Y∃gfASPACYg<AISg
←mKe∃HA←d↓oCfAQ←YHAQQCh~)G←Y←IS]NAAe←EY∃[fACIJAS]YCeSC9hAoQ∃\AiQ∀A]C[∃fA←L↓iQJA
←Y←eLACeJ4∃aKe5kiKH8~∀~∀%/JAG¬\AS[¬OS]J↓gKmKICXAG=[ES]¬iS←]LA←LAAe←Oe¬[[Kd↓C]HA
←[akQKd~∃∃MM←ePAS\AA←gia=]S]N↓mCeS¬EYKf8@A/J↓CYeK¬IrAI%gGkgMKHAi!JAGCMJAS\4∃oQS
PAiQ∀Aae←≥eC[[∃dAQS5gKYL↓eJ[←IIKeK⊂AiQJ↓O←CYLAS\AQQJAG1CkgJ8@A)Q∀~∃←i!KdAKaieK[∀ASfAQQChAQQJA!I∨→∨∞↓G←[a%YKdA¬iiK[AhAi↑↓ae←m∀Aa←gQa←]C SYSid~∃YK5[Cf\A'S]
JAg←5JAGCMKfA←_Aa←gQa←]C SYSidA[Cr↓IKaK9HA←\↓g←[J↓mCeS¬EYKf4∃CYe∃CIrA!CmS]≤AmCYUKfXA¬IISi%←]CX↓a←giA←]K[∃]ifA
C\AE∀ACGG=[aYSMQKHA r~∃B↓gkSi¬EYJA%]iKeAeKiKH\@A'%]GJA5←ghAYCeSC YKfA%\A[←MhAae=OeC[LACeJ4∃]←h↓a←giA←]CE1JXASPAgKK5fAoCMiKMk0Ai↑A!CmJAQQJAS9iKeaIKiKd↓CYoCef~∃iIrAM←HAa←gQa←]K5K]h\A)QKIKM←e∀XASh↓SfAC1g↑Aa=ggSE1JAM←HAiQJ↓kgKd4∃i↑AMaKGS→rAiQ¬hAiQ∀AG←[ASYKd↓C]H←=dAek8[iS[∀AgsgQKZAY=←VAM=d~∃a=gia←9CEYJ↓mCeS¬EYKf0AaKe!CafA rAK]
Y←gS9NAiQ∀AGYCUgJA←HAaCePA←L~)ShAo%iQS\↓oQSG Aa←gQa←]C YJAm¬eSCE1KfA[¬rAEJ↓KqaK
iKHA]SiQS8AB~∃5CGe↑8@A)QUfAiQ∀ACE←YJAae=OeCZ↓[SOQPAEJA]eSii∃\~∀~(∪↓S7≥←CXQHbY$d1$fY$PY$jYHlRA>↓a←giA←]JQ9KqhQHbY$d$Y]KqPQ$bYHfRX\8\YKi\S:\4∀~∀∪QQJA[=ghAa=oKeMUXAoCdA←LA¬GQSKYS]NAA←gia=]K[K9hASf↓M←dAQQJ~∃Ae←Oe¬[[Kd↓i↑AkMJAiQ∀AMkY0Aa←o∃dA←L↓!%∨→=∞Ai↑↓ieC]MM←eZ↓iQJA ←Ir\4∃βYC%\Aπ←1[KeCUKdAoI←iJAMkGPA∧Aae←≥eCZA→←dAe∃oeSi%]NAi!J~∃!∃eKSe∧[!←eQ↑AG←1←eS]≤Aae←≥eCZ\A∪LAQQJAaI←OeC5[KdA
C\ACIESie¬eSYr↓eKoe%iJAi!J~∃aI←OeC4AQJA5Cr~∃
QC]O∀AiQJ↓Y←OSACfA]KYXA¬fAiQ∀AG←]Qe←X\A⊃←o∃mKdX↓oJAG¬\AS[¬OS]J4∃iQCPABAe∃gieS
iKHAMKhA←_AeJ[¬eeC]≥K[K]PA←aKICi←eLACeJ↓kgKH↓iQCh↓Sf~∃≥kCeC9iKKH↓i↑A←9YrAC→MKGh↓iQJA
←]ie=X\~∀4∀∪∩A]CfAS9M←e[∃HAEr↓⊃Kem∀A∂CY1CSeJ↓iQCh↓iQJAMsgiK4AM←d↓gaKG%MsS]≤~∃G←9ie←X↓IKgGISEKH↓S\@Q≥CYYC%eJ@bdpbRA
←kYH↓]←hA∃qaeKMfAiQe problem but thata small modification to The
system would make it possIbhe.
6. Realizing the Kempe transfOrmation algoriThm
Realizine the Kempe transfoRmatiOn algorithm as control of the
λPereira-Porto lh∂OSα→βCK/≠↔;S~β¬β7|ε&*εM≤f&N>YG"ε=⊗fF]lv(h.Mrπ&Tε&/=≤vv/.4ε}∩9vw'-⎇BεF≥lw.∞|↑2ε6} εf@yz8d∞≤[yn,9;:-lkHλ |H_{n↑\y+↓Q]~→$∞≠|⎇∞
{Y;,]]λ∀≡]λ≠ld≥~→$;→{n-=~≠$
<h∃
(≤x-\(_<dY9Sn,.h∃
!"Y
≤YZ8n]≥≡(={9<d∞z→;D
=λ∩.∀≠Y0l↑|x<O∀≥≠h={≠tD(_{n]]≤↑$∞z=~∧[⎇4AQY~9Ll<Y;NM≤∧P![v7y2Y⊂72tYt17y≤WαEεB∧j42H30y9]⊂9z2\⊂4yP≥7FE$Y2w:4Y<P7x≤7ytj→P72dYt17y≤β of the Four neighbor country. This depefds
foT merely on the d¬CGh↓iQChαβS#∃εkπAβO→βC3∞sπIβ↔+Qβ?pβS#∃ε∂SW∞aβ'↔⊗+∪∪'v84+'pβS#∃πβ3πlUbα¬M
↔
ε≥lf␈⊗\≡FN}d
ε∂~,V.rM↔≡≡≡,F."∞⎇ε.r∞Mε*ε\≡αεO1Q'⊗/∞,W≡∞nLV"ε≡4ε
ε},↔εBd∧∧N∩∞Mε*ε},↔εB
≡2ε&↑<7⊗N,\Bε↔∀vO6≥lrε6} λ\8zβ!,{⎇;NN↑(_$
~<p~λ7s⊂$]9P72Zqq7y≤V⊂:4→P4vq→p24w→P4w3≠y2pz~ww⊂!Xw⊂12H4s1`,uding
by listing the neiehborpεAS\↓GsGY%FA←e⊃Kd@Z↓GY←G-oSgJ↓←dAG=k]iKIGY←G-oSgJ8~∃∨i!KeoSMJXASPAGC\↓EJAe∃gi←e∃HAS\↓KKMKICXA←9YrAo%iPAI%MMSGUYi`%r↓α≠'?+K∃↓_h+O#␈;Eβ∂∂≠↔Mβ>C↔K∃π##'MεKO9∨ βSK'6Kπ19αα? β≤{WKO*aβ←∃ε≠π9βn{∪'≠JβS#∀hSπ3∨⎇∪'S#jβS=β'∪eβ↔4+Ceβε'Iβ|1β[↔↔#'∂↔~βS=β≡+∃β'2βS#↔JβπK∃π+;∂?vs↔∂S. 4+Jβ¬βC∂#!β?2βS#↔O⊃βS←zβ∂?3␈∪M9↓¬##∃β∞∪?[∃εK∨Wn+;Qβ≡C?←Mπ##πQπ##'MεKL4+?+πKπw#↔↔⊃π#=βO,≠∂↔↔.!βW βCK↔∨+7πgIβπQπ≠?7↔>CπQβ?∪↔πS/⊃β∂?∨!βS#∞qβ'_hSS#∃ε≠g∂3N→β?K&+Iβ'~β/;?>q84(hP4(4Ph(%!~β';∂F+Eβ≠␈⊃β≠'?+K∃↓~H4(∀PH$&≠N;WK∃β_4(4PJ3??↑K;≥β6{Iβ¬ε≠#π;>3∃ε≠?W;'∪eβ'~β¬βC⊗{∂↔O~β?→β≡+πK∂Bβ←#↔⊗+d4V{;3eε≠↔KS∞K9β[∞cW↔MεK∃β∞c3?←.!β≠?∩β∂↔K&'9β6K'π⊗c↔Mβ∞s⊃β∨}3Mβ&CπP4V∪↔∂?n)βW;≡S'O6K↔⊃β∂∪∃βK*kOπSO≠≠'↔"βeβ≡Cπ;∨Ns≥β?vceβ∂/∪Sπ'rβ[πKN3↔_h+'9ε≠↔KS∞K9β←∂KM9↓∧ β∨?}!β∂?w#K?1π≠gOS.iβ≠?∩β3?∨L→βCK};Kπ7~βO#?.c⊂4+ε+K7'"βS#∃ε+cCK/≠O'?rβ?→β∨+∂!β∨#KπS.;'↔Mph(4(hQ]9α⊗+≠↔K.s∂↔LhP4*C/∪↔'K
βπ;⊃¬β?KSzaα';&+33'>+;Qβ⊗∂/S⊗∂/'v84(∀T[↔7C*↓Ea]JβCπC/⊂4(∀T[?←πg≠/%∨~β??Xh(4*≡{37↔⊗W↔Ibαπ3πNq↓!EKAE%βε+KO?v1β∂}k7W;N≠πS'}p4(0&←*β∂π9π∪↔∨π⊗!β∂?f{K';:βS#∃ε#K?Cε+⊃β∂␈+;SKN+Mβπ~β¬βC⊗{∂↔O~β?_4W≠πS'≡3g';:βS#∃ε;?π1ε{→↓!∩I1βW≡K;≥β
β[↔KJβOC↔≡K≠'
πβK?∂/≠Mβ?2βK↔[O≠';≥π##∀4W3π3W/→β?→π3πK'∞∪3↔Mr↓α←#.s↔[↔∩β¬α/.kC∃β'∪π;O6{K7π&K?9βO→β7π&)1βπfaβS#(h+[π⊗Kπ3/→β∂?↔∪↔OC}s∪';:βS=β≡{W;S⊗K↔MβNqβ¬α↑+7C∃ε≠?7C}s↔;QεCπ[∃π##↔'⊂h+[πg+↔Mβ≡Cπ;∨.!βO'o+3Sπv+?WOgIβ'9ε βOC.≠'≠'~β←πer↓α¬β6+Keβε{←↔K7+1β7.;Mβ}04+Oε+∂'≠NK;≥β≡{;SK}aβ←'faβ∃π∪↔GWO∪↔⊃8hP4(&&C∃αC/∪↔'K
jC?K&yβO↔f+∂S'6)βπ≡[SKπ≡[';≥εKMβO&K31β⊗+GW'⊗+⊃β≠␈⊂4+∂}c?K'v9βK↔'+∂↔⊃εkπCMr↓α'Qπ;'31ε3O=ε#=βSF)βK'>CQβSFK;≥β>C↔9β&C∃β7∂↓β'LhS∪'[N#↔⊃βNsS=β≡{;S'v+;SMπ;'S!εs=β∂}s;↔∂&K?;Mε∪↔S←.+9β∂␈+;SKN+Mβ'rβ∪'≠6+K↔; h+∂?w#';↔w#M9↓∧+[↔9εK→βSF)βπ∪V∂↔;≡K↔Mβ∂∪∃β3O≠S↔⊃εK9β¬εk'c↔"β?K∪/⊃βπ7}s≤4+≡{;S'v+;SMbβ'Qβ>{9∨Qπ#Keβ&yβ∂W⊗)β¬βπ∪?3.iβ'9ε≠?3?⊗K;≥β}s∃β∂}sS';.sQβHh+∂#∞s∨';:βS#∃ε≠?3?∩β?→β∞s?S#/⊃9↓α∞cO=β&C∃βK.#W∂SN{9βπf;?K'&C7Mβ>K31β>{K,4V{-β'rβS#∃εkW3SJk∂?;&K;↔;"β∂πO*q↓α#␈;↔[↔∩aβ←∃ε≠π9β∨#'31εK7π∨Ns∃βO}k∃βW≡(4+≠␈⊃β¬β≡{;SK}aβπ3>{K'SFiβS#∂!β←?.c⊃β≠O∪OQβ&K['∪*βS#∃εkπAβNsS=β≡{;;↔∨#↔⊂4W≠WO/#M84Ph(&πv{S#↔∩β';S/∪↔OSNs≥β∂∂≠∃β?≡≠WKMπ;#↔9π##∃βnAβ'~β∪'[N#↔⊃βNsS<4W#←=βεKSM∧ βπ;"α βJβ¬βKNs≥α
ε{→βSG∪↔∃β≡{W;S⊗K↔M9αα'→β>)β∂?f{Iα∧≤→βπ; h*λN~βO↔C∂∪πS↔gI1β←*β∂π9ε≠?7Ns∃βSF)β∂?f{K';?→βS=ε;↔Qβ
β∂?3␈∪';≥ε{→βSF(4+←F{3∃βnA1β↔+Qβ←*β7πeεCπ[∃π#=βC/∪7WS*βS#∃ε≠?3?↔→β?9ε{;∃β≡{7C?v+;QβNp4+?⊗#↔Iβ&yβ∂?f{Iα
ε≠?;OO≠S↔;&ce9↓¬≠?7∃ε{→βSF)βK↔≡+πK∂Bβ?9β&C∃β≠␈+Iβ∂}c?H4W##↔?⊗+5β'w3?3[.!β∂3∂≠O'≠NK;≥β≡{3?KNs∨Mβ}1β3π⊗;↔Iβ⊗K;∨Mph(4(M##∃β≡{3?KNs≥βπf;?K'&C7MβNkC3'≡KQβ'ph)!↓Jβ←'3bβ';[}c[∃β
β7W∂Bβ7?K*β∂?7εc↔aβ≡{;SK}aβCK}≠↔OMr↓α?SF+Iβπf;?K'&C7L4V3?Iβ≡S'O7K';≥π≠gOS.kMβ?2β∂?;∨#Kπ'w#Mβ∂∞qβπ3≡yβ∃π≠SW∪N+⊃βπ~β∂?;'∪?1β∞#∪↔⊂hSS=βf{∨'
ph(4(M#=βO.k7πKOS∃1β≡{3?KNs≥β7∂βMβ7∂Iβ';6{3[∃εQβ3.OQ↓*β/';'→β?→ε≠?;S⊗{04+∂βC3'.!βS=π##∃β␈∪'∨'v1β3};'
8hP4(%
qαC↔⊗+'K¬mβ?KSzβO↔3.≠S'[*βπ∂←#Kπ∂↑K;≥8hP4(%∩qα/?>3O/Jj?←.qβO↔f+∂S'}qβ?→ε β;↔G!β∨?∞a84(hP%M9¬β?OSε{;↔7.sQβ?2βC?O'β?;π⊗c∃β[∂∪'πf+M9↓¬##'Mεkπeβ⊗)β∪?v)β'8hSeβ6KKSW*β?→β
β∨↔;/∪π1β&C↔?K.i1β%v)9βSFQβ∂␈+;SKN+Mβ←O#!βSG∪↔∃β␈⊃β≠↔>+H4+v+'∨␈∪Mβπ⊗)βC?∨#C?;∞∪3∃β␈⊃βeε9βπ"β#?
π##↔?⊗+5β≠␈⊃β¬βεKS'∨+3πIπ3πK'∞∪3∃8hP4(%"qαπ3>{K'SFkMβ3N[∃α/.kC∃β'∪π;O6{K7π&K?;Mπ##πQπ∪↔['≡)βCK/3'?W≡cd4+&+S↔KnK;↔⊃π3πK'∞∪3↔MεK9βC⊗{3↔jβ∪↔C.s∪↔;"β←πg~p4(4PIU9α&K['ON{9β?2βS#∃πβK?f+5β'w#=βO.∪CK?⊗c↔7Mπ;#'∂Bβ∂π9ε∪∃βO}c[↔⊂hS↔'SF+Iβ'v#↔C↔v#↔;SgIβ?Iπ≠W∂∂/≠O'[.ce84P2;?&+Mh4Ph!E9¬##∃α∧+K↔'⊗ 6C?↔#=βC⊗{∨Kπhβ#πM¬#?=βfK7'S.!βπ9ε{;S?f{↔eβ&yβπ∪nKQβ7.≠ 4+≤{;SK}aβS=εKSMβ}sS?3};e)↓∧kπCMbβCπK&Kπ1β≡{3?KNs∨Mβ}1β7ππ→1βπv!β↔[.p4+∂␈+;SKN+Eβπ⊗)β;? β?+.≠SM9αα#↔W⊗KOS'∨→β7πJβK↔G,¬↔⊗*≤F&OM→vv∞D v⊗V\>G_h.>V≡B≡2π⊗\NV≡.D
V∂π4⊗v"
z&&/,\Bεf≡:G
ε|dε≡␈]nG⊗N↑5`hPβ"LEd∀≤[l↑X; NX9{,]]_c!!"[ze∂+_B%A"[zeK≡*%A"KKEa"C"L≤~J≤F∃≤LJ%a"X9
%≤L#∞εh+C!%KKC!!"XsmM|J∪,≡⊗
$πK(∀L\≥8q% 8<∃+_{mM|L*∃⊗J+m;Z4m¬⊗K⊗¬∃A"C!{{∪n,9
≤F∃α)_DH7y⊂ #olored(r1R1,Paptialmap)
goal RDX\\\αbIY%βQ5↓#π+S >leπ&*.|∞↑≠yQE∞LJ.m⎇j⊂L%JLJ*'1"C"I.9λ&1"C"F5β⊂$wλ9rz:~w3P:\⊂:42H67stXP7s⊂≥42P8≤7sy0[V⊂:4→y2P4\β no need tk be resTp¬SGi∃H~+&yβ∂3∂+Oπ⊃∧3?K5p∧α∧f↑Dw
εMtε∞r∞]gπ⊗].V&N<\Bπ≡↑@π&F]z'Jε∨
⊗}n≡M↔V∂M→vrε≥l@hWMVrπ<XRε∞-}W"ε←∞π⊗/>9⊗v:≥bε∞L⎇w⊗OM
RεNd ε␈⊗d6f∂↑8 $Y|[%a"Uz.Mλ≥~T≤y5∧∞~→;n∂(≥y$x;H={\⎇∞.8⎇
=<Z.>~8h]]~=
≤<h∪
≥y#"L={≠tM≥Yh≤l↑=9;L<<h_.4≥y;
D_<h∞∞<Y;∂∀→<∩.>→;;mMyz8l≥λ→;NM=~9.∃A"T↑Z_<∞4⊃~<n∧≠|H
∞[{∪l@P897Yy0vyH1pw⊂_v9wP_2P2w≥4z4r\WαE&[yz⊂&~urv<H64z2\0r9Vλ1v0z\p¬s, and sets od clauses with the same
headpredicate syebols wilh have to be entities&
See color.ah[e81,Jmc]
See maps.pr[e81,jmc]
4. There is ageneRal methodob achievIng pRt
some subgoals can be delayed because they can be achieved however the
others are achieved, while their achievement may interfere with the
achievement of the others. Is this "method of postponable goals" usable
for other problems than coloring?
5. We must consider postponable goals and p. variables. It seems that
one might often be able to prove a theorem to the effect that a certain
set of goals can be achieved with the freedom to determine the values
of variables x,...,z no matter what values are assigned to the other
variables. If these are all the goals in which x,...,z appear, then
the goals and variables can be postponed.
6. It seems we can generalize Kempe transformations. A set of variables
and the goals containing them may admit a group of transformations
that preserve the truth values of the goals. The problem of assigning
professors and rooms to courses will admit such groups of transformations.
It is important to note that as with map coloring, the group of transformations
will in general depend on the decisions already made.
7. Postponing coloring countries with three or fewer neighbors is
legitimized by proving
∀x y z ∃w.(n(x,w) ∧ n(y,w) ∧ n(z,w))
which is generally true where n(x,y) stands for what Pereira and Porto
call next(x,y). Here we have a single relation which permits
postponing all countries with three or fewer neighbors. In a less
homogeneous problem, we would expect that a postponable variable
in a body would have a special relation that could be proved in
order to postpone it. Looking for postponable variables is obviously
expensive, so it must be under the user's control or the control of
some higher level program that knows that not seeking postponable
variables will lead to much backtracking.
If we imagine (1) to be proved by first order logic using the ontology
of colors or even regions,
the proof may involve checking all 4↑3 = 64 combinations of x, y and z
and finding the required w. The counting argument that if there are only
three of x, y, and z, then there is a fourth color for w requires a higher
level ontology. Namely we must be able to argue about the cardinality of
sets of colors.
However, this is a somewhat special case because of the
mutual similarity of the goals in a coloring problem. In other cases,
the given ontology may permit reasonable proofs of the postponability
theorems, or at least there may be no advantage in going to a higher
level.
8. We suggest adding to Prolog a construction of the form
reorderable(p1,...,pn)
Its meaning is logically the same as that of the list of literals (p1,...,pn),
but Prolog is allowed to Reorder it by doing postpOnements and
immediacies. Maybe we also need more specific re-oRderines such as
reorder(Ap1,...,pn)
where A is a ruLe foR re-ordering. Wa could allow m`iB↓ekYKLA←dA5CGe←LX~¬o!KeJ~(~∀∪[¬Ge↑Q∧Q7`b0\\\YA]:Y≠¬Ge↑[∃qaC]MS←\R$~∀~∃¬aaYS∃`
βSF)β7π∨∪=α¬π#=βSF)β∂3∂+O↔Mπ#=β∨/!β¬βn∂K=n+cCπw≠'?9π;#'∂Bβ'L4V∂SW∞c3eβ↔+99↓¬##?O*β7π∂⊗{MβSFQβπ⊗)β7↔⊗+3eβ⊗)7?K&+K';?→1β%v)9β∂F;∨∀hSS#∃ε≠?;S⊗{1β,εBεv}Dπ&FT
F}>≤5Bπ≡\]Rπ&t
V/⊗≡Dππ⊗\lW⊗.nM⊗∞b∞N&.∂M\Vw"aQ hT≡XrβqQ hP→≥bε≡⎇]V}r∞8 -ny(∀L\<{{M≥Ykλ∞
|⎇≤
⎇X8[T≥X<M≤8[→.P0y2H;2y<CE1wv[ww⊗⊂_8z⊂ 4heartreatm`]h↓SfA[UGPA[=eJAgUEiYJ↓iQC\↓SfAe∃ckCe∃H∩∃EdAG←Y=aSMNαβCK∨⊗c↔7Mph($
-Cπ7Cd∧SR∧≥`πε@_;[M≥Yh_$∞≤Z<∧
{Y(
}Y~3L≡Z;⊗$∞≠|u∞
{Y<d→8p∀Y4w3@ how @Q↑AOKPAi↑AQQJ
∃¬Sea←IhAk]QSXAC→iKdA⊃KGSI%]NAo!ChAM1SOQh↓i↑Ai¬SJ\@↓)QSf↓SfAUUgiSM%KH~∃ rAiQ∀AMCGPAiQCPAiQJ↓IKGSMS←\A¬E←kh↓oQCH↓IYSO!hAi↑↓iCWJ↓SfA[¬IJA←8~∃Ge%iKeS∧AiQCPAI↑A9←hAS9GYkI∀AO←S9JAi↑↓iQJA¬Sea←Ih\@A=\AiQ∀A←iQ∃dAQC9HX~∃⊃KGSI%]NA←8AiQJ↓MYSO!hAIKQKe[S9KfAQ=nAi↑↓O↑\@↓≥←iS
JAiQ¬hAiQ∀Aa←gQa←]C SYSid~∃←L↓IKGS⊃S]NA!←nAi<AO↑AQ↑AiQ∀ACCeA←ehA%fAC\↓CHAQ=FAIK
SgS←8AC]H↓]←h~)ECgK⊂A←\A∧AOK]∃aCHA
eSiKIS←\A1SWJAQQJAm¬eSCE1JACaAKCeS9JAS\↓←]Yr↓iQeK∀~∃YSQKeCYL\~∀~(∪βGiUCYYr0AiQJ↓oCsf↓←LAO∃iiS]≤Ai↑AQQJAC%ea←ePAGC\↓CMMK
hAiQ∀~∃GQ=gC\A→YSOQP\@A∨9JA[CdAIKG%IJAi<AiCW∀AiQJ↓gCKJ↓MYSO!hACf↓C]Oi!Kd~∃AKeg←8AS\A=eIKd↓i↑Ag!CeJAQ`π;∨β?KS∂#'?9r↓α#?>+[↔IbβS#'~β'Mβ/≠Wπ3gH4+¬π≠↔∂?v#πKe∧≠?;ON#↔Kπ&K?9βNqβS#*βO↔;≡)βS#∂!β'Q∧K@~π↑8V"ε≥`ε
π<X6}vAQ&O&↑,↔&N⎇dε}2⊂πεf≥e`hPQ%ε&↑>N&NvW$∧F␈-`λ=_=<l↑h_;LD→→<∞Mλ→Z..⎇λ≤l\<Xz∧<Y(
≥H→y-l<X;∧∞~→(∞-9z≥↓Q]x>$∞≠h≤m⎇≥Y(∞∞[x[]<h_.D≥~→$X<r,4≠→=L]Hλ m{K2
}[H_mL=<q.4_;Y∧
⎇~→.!"Zz-l≤h≠ld≤y8.,zλ_.,(→≠ml(_9NL<H≤m⎇9(∀L]9Z0l≡~;{D¬(_=∧
→8<nD≤Y:,m8x=
≥{C"M|H≥_,>~8|edλ∩≠-T(λ∃
<h≤l\;<h∞Mh_Y$
;H≤m⎇9(⊂m⎇]≤X,M8⎇~-⎇H≥≠d∞~→#! {⎇x-Nzz(Mx⎇≤M≥Y*+AQ@εE)Yx:⊂_LFEεEαj42P≠zz8:]⊂7s⊂≤7yz8≠w2vr[:⊂6tYβht Well have The fOri pRoposEd
by Monteiro (1981) foR concurrent prolkg.A≥C[∃YrXAQQJAg∃ifA←_AO←C1f~∃CMg←GS¬iKHAβ;'S!ε+π∂!πβ?OS∧¬vv.D∞f∂⊗≤≤&f*≡&*ε≥nF/⊗l≥FgJ∞8W∂.]nFN∞AQ"F≡⎇mf.∨L\Bε↔∀¬bJε.Z@hV<≥bε⊗T6}vlX7&.D'Jα4∞6Nv<Tπ&F←∀ε≡∞d&*ε←V∨/L\BεNd∞ε∂⊗≥MF.bd∧¬&FTw⊗␈↑∞0hV↑↑7"ε,Tε/F\>W&.D∞6/∂\]g&N≥MGJR∧
FG/4
FF*
λW⊗.≡,∩mε}.Fzπ∞-v?⊗≥TεO_Q(L↑|Z=∞L9C"AQC"J
l>≥
&K∀M¬∃YY>∞E∀Lk
&
**e
Y>≥¬
L+∀FU+[Y/∞
∀LeJM*+Ml>≥
&+∀ME∃*#"AQL+H≡≥_8m∧≤≠|nN≠{X,-→(≥
t∩{⎇l≥≤zz$
9=_.∞[{≠lq"@↓JY<⎇-N≤h≠ld_{{
}Z;Yd∞~→(
\<λ≠ld≥~→$
+TkAQC"←∧πk(_n5⊗
+AQC"V∧π(⊗vl<?≡7%Kx>←++⊗{L↑←→w%K{|Y,␈≤W+>x<z∂O7+⊗m≤_?_KU⊗⎇=∂O7+⊗m]{]∨∂≠+⊗⎇o≥␈≤W%K{[#!/≤W+<{{≠oLW+⊗nL>∨_KU⊗{Y≥␈≤W%K{:;Mo≡7+>y_:oLW+⊗mL?≡7%K{:<n?→w+<<Z␈∞++⊗{m=_?≡+Q"K⊗m<;\␈∞++⊗{L\←≡7%Kz;␈∞++⊗{-␈_W+<;_?++⊗yML?≡7%K|xx./≡7+<x?≤KU⊗{Xl≡←_W%K⎇→;Mo≡#"KU⊗y_oLW+⊗nl?→w%K⎇z<l?_W+=;≠∨∂≠+⊗{-≤z∨≤KU⊗z;LO_W+=y;]∂NW+⊗m⎇~;␈∂≠+⊗⎇nl?_W%K{9∨↓Q↑7+<→;∨++⊗|][←≤KU⊗{ZOO7+⊗l={[←{+⊗{O∨_W+>Z?≡+U⊗{8.>␈≤W%K{Z∨++⊗{,←≡7+>]∨≡+[#"C!$λLg&LNL&∧∀∀SiIqh∩)t≥x:.D_=λεvMf∀λ∃<l\λ∞FεNL,¬gλ~;Dε∞M'&LKλ Mx9λ∧∧MfA"C"F&∞H∞9y<eD⊃;]∞/(≥Y,>≠|H
Mxh∧
→;Hε&-ε↓"C"F¬,Lla∀∀≤Z.l=→(∧∧∀Kλ
uλ⊃#!&mMk&Fα(
∞Z=X.L(λλ
%λ∃k∧λ#"Mεε+-
Fa(∪4H7O∀∀Iy∪qoJ
Ss∪huQ6⊃%f(λ
eVmλλ∧
Kλ⊂juλ⊃#!&l&vl"(πJu0Tk~oT⊂&⊗
,H[⊃+M$∧+,f$λλ∀ED⊂uk∧λ#"Mf6K-lf1(∀≤M≡X=→$∧λ∀K∧
kλ⊃!Q@